/*
起源
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象为数学问题
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

     +
    +++
   +++++
  +++++++
 +++++++++
-----------  -----------  -----------
     A            B            C

解:
1. n == 1
第1次 1号盘 A---->C sum = 1 次

2. n == 2
第1次 1号盘 A---->B
​第2次 2号盘 A---->C
​第3次 1号盘 B---->C sum = 3 次

3. n == 3
第1次 1号盘 A---->C
​第2次 2号盘 A---->B
​第3次 1号盘 C---->B
​第4次 3号盘 A---->C
​第5次 1号盘 B---->A
​第6次 2号盘 B---->C
​第7次 1号盘 A---->C sum = 7 次

规律：
1个圆盘的次数 2的1次方减1
​2个圆盘的次数 2的2次方减1
​3个圆盘的次数 2的3次方减1
.....
​n个圆盘的次数 2的n次方减1

故：移动次数为：2^n - 1

https://dmego.me/2016/10/16/hanoi

解题思路：
- 要把64个盘子从A座移动到C座，需要移动大约264 次盘子。一般人是不可能直接确定移动盘子的每一个具体步骤的
- 老和尚会这样想：假如有另外一个和尚能有办法将上面63个盘子从一个座移到另一座。那么，问题就解决了。此时老和尚只需这样做：
  1. 命令第2个和尚将63个盘子从A座移到B座
  2. 自己将1个盘子（最底下的、最大的盘子）从A座移到C座
  3. 再命令第2个和尚将63个盘子从B座移到C座

第1个和尚的做法
1. 将63个从A到B
     +
    +++
   +++++
  +++++++
 +++++++++
-----------  -----------  -----------
     A            B            C
2. 将63个从A到B
                  +
                 +++
                +++++
 +++++++++     +++++++
-----------  -----------  -----------
     A            B            C
3. 将1个从A到C
                  +
                 +++
                +++++
 +++++++++     +++++++
-----------  -----------  -----------
     A            B            C
4. 将1个从A到C
                  +
                 +++
                +++++
               +++++++     +++++++++
-----------  -----------  -----------
     A            B            C
5.           将63个从B到C
                  +
                 +++
                +++++
               +++++++     +++++++++
-----------  -----------  -----------
     A            B            C
6.           将63个从B到C
                               +
                              +++
                             +++++
                            +++++++
                           +++++++++
-----------  -----------  -----------
     A            B            C

第2个和尚的做法
1. 将62个从A到C
     +
    +++
   +++++
  +++++++
 +++++++++
-----------  -----------  -----------
     A            B            C
2. 将62个从A到C
                               +
  +++++++                     +++
 +++++++++                   +++++
-----------  -----------  -----------
     A            B            C
3. 将1个从A到B
                               +
  +++++++                     +++
 +++++++++                   +++++
-----------  -----------  -----------
     A            B            C
4. 将1个从A到B
                               +
                              +++
 +++++++++     +++++++       +++++
-----------  -----------  -----------
     A            B            C
5.                        将62个从C到B
                               +
                              +++
 +++++++++     +++++++       +++++
-----------  -----------  -----------
     A            B            C
6.                        将62个从C到B
                  +
                 +++
                +++++
 +++++++++     +++++++
-----------  -----------  -----------
     A            B            C

第3个和尚的做法
第4个和尚的做法
第5个和尚的做法
第6个和尚的做法
第7个和尚的做法
……
第63个和尚的做法
第64个和尚仅做：将1个从A移到C

移动 3 个盘子全过程
1.
     +
    +++
   +++++
-----------  -----------  -----------
     A            B            C
2.

    +++
   +++++                       +
-----------  -----------  -----------
     A            B            C
3.


   +++++         +++           +
-----------  -----------  -----------
     A            B            C
4.

                  +
   +++++         +++
-----------  -----------  -----------
     A            B            C
5.

                  +
                 +++         +++++
-----------  -----------  -----------
     A            B            C
6.


     +           +++         +++++
-----------  -----------  -----------
     A            B            C
7.

                              +++
     +                       +++++
-----------  -----------  -----------
     A            B            C
8.
                               +
                              +++
                             +++++
-----------  -----------  -----------
     A            B            C

由上面的分析可知：将n个盘子从A座移到C座可以分解为以下3个步骤：
1. 将A上n-1个盘借助C座先移到B座上
2. 把A座上剩下的一个盘移到C座上
3. 将n-1个盘从B座借助于Ａ座移到C座上

可以将第(1)步和第(3)步表示为：
- 将“one”座上n-1个盘移到“two”座(借助“three”座)。
- 在第(1)步和第(3)步中，one 、two、three和A、B、C的对应关系不同。
- 对第(1)步，对应关系是one对应A，two对应B，three对应C。
- 对第(3)步，对应关系是one对应B，two对应C，three对应A。

把上面3个步骤分成两类操作：
1. 将n-1个盘从一个座移到另一个座上（n＞1）。这就是大和尚让小和尚做的工作，它是一个递归的过程，即和尚将任务层层下放，直到第64个和尚为止。
2. 将1个盘子从一个座上移到另一座上。这是大和尚自己做的工作。

编写程序
- 用hanoi函数实现第1类操作（即模拟小和尚的任务）
- 用move函数实现第2类操作（模拟大和尚自己移盘）
- 函数调用hanoi(n,one,two.three)表示将n个盘子从“one”座移到“three”座的过程(借助“two”座)
- 函数调用move(x,y)表示将1个盘子从x 座移到y 座的过程。x和y是代表A、B、C座之一，根据每次不同情况分别取A、B、C代入
*/

#include <stdio.h>
#include <stdlib.h>
unsigned long long int i = 0;
int main(int argc, char *argv[])
{
     void hanoi(int n, char one, char two, char three);
     int m = atoi(argv[1]); // 利用命令行参数输入汉诺塔层数
     // printf("the number of diskes:");
     // scanf("%d", &m);
     printf("move %d diskes:\n", m);
     hanoi(m, 'A', 'B', 'C');
     printf("all step : %lld\n", i);
     return 0;
}
void hanoi(int n, char one, char two, char three)
{
     void move(char x, char y);
     if (n == 1)
          move(one, three);
     else
     {
          hanoi(n - 1, one, three, two);
          move(one, three);
          hanoi(n - 1, two, one, three);
     }
}
void move(char x, char y)
{
     ++i;
     printf("%lld : %c -> %c\n", ++i, x, y);
}